{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numpy import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 数据集\n",
    "def loadDataSet(filename):\n",
    "    dataMat = []\n",
    "    labelMat = []\n",
    "    fr = open(filename)\n",
    "    for line in fr.readlines():\n",
    "        lineArr = line.strip().split('\\t')\n",
    "        dataMat.append([float(lineArr[0]), float(lineArr[1])])\n",
    "        labelMat.append(float(lineArr[2]))\n",
    "    return dataMat, labelMat\n",
    "\n",
    "# 随机选择alpha\n",
    "# 参数值：alpha下标，所有alpha的数目\n",
    "def selectJrand(i, m):\n",
    "    j = i\n",
    "    while j == i:\n",
    "        j = int(random.uniform(0, m))\n",
    "    return j\n",
    "\n",
    "def clipAlpha(aj, H, L):\n",
    "    if aj > H:\n",
    "        aj = H\n",
    "    if L > aj:\n",
    "        aj = L\n",
    "    return aj"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-4-a8ef318a4372>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mdataArr\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mlabelArr\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mloadDataSet\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'testSet.txt'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      2\u001b[0m \u001b[0mlabelArr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-2-1b3d20d8c2dc>\u001b[0m in \u001b[0;36mloadDataSet\u001b[1;34m(filename)\u001b[0m\n\u001b[0;32m      7\u001b[0m         \u001b[0mlineArr\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mline\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mstrip\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0msplit\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'\\t'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      8\u001b[0m         \u001b[0mdataMat\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mfloat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlineArr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfloat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlineArr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 9\u001b[1;33m         \u001b[0mlabelMat\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfloat\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlineArr\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     10\u001b[0m     \u001b[1;32mreturn\u001b[0m \u001b[0mdataMat\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mlabelMat\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     11\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "dataArr, labelArr = loadDataSet('testSet.txt')\n",
    "labelArr[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# SMO算法简化版\n",
    "# 参数：数据集，类别标签，常数C，容错率，取消前最大的循环次数\n",
    "def smoSimple(dataMatIn, classLabels, C, toler, maxIter):\n",
    "    dataMatrix = mat(dataMatIn)\n",
    "    labelMat = mat(classLabels).transpose()\n",
    "    b = 0\n",
    "    m, n = shape(dataMatrix)\n",
    "    alphas = mat(zeros((m, 1)))\n",
    "    iters = 0  # 该变量存储的则是在没有任何alpha改变的情况下遍历数据集的次数 \n",
    "    while iters < maxIter:\n",
    "        alphaPairsChanged = 0  # 用于记录alpha是否巳经进行优化\n",
    "        for i in range(m):\n",
    "            fXi = float(multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[i, :].T)) + b  # 预测的类别\n",
    "            Ei = fXi - float(labelMat[i])  # 误差\n",
    "            if ((labelMat[i] * Ei < -toler) and (alphas[i] < C)) or ((labelMat[i] * Ei > toler) and (alphas[i] > 0)):\n",
    "                j = selectJrand(i, m)  # 随机选择第二个alpha\n",
    "                fXj = float(multiply(alphas, labelMat).T * (dataMatrix * dataMatrix[j, :].T)) + b\n",
    "                Ej = fXj - float(labelMat[j])\n",
    "                alphaIold = alphas[i].copy()\n",
    "                alphaJold = alphas[j].copy()\n",
    "                if labelMat[i] != labelMat[j]:\n",
    "                    L = max(0, alphas[j] - alphas[i])\n",
    "                    H = min(C, C + alphas[j] - alphas[i])\n",
    "                else:\n",
    "                    L = max(0, alphas[j] + alphas[i] - C)\n",
    "                    H = min(C, alphas[j] + alphas[i])\n",
    "                if L == H:\n",
    "                    print('L == H')\n",
    "                    continue\n",
    "                eta = 2.0 * dataMatrix[i, :] * dataMatrix[j, :].T - dataMatrix[i, :] * dataMatrix[i, :].T - dataMatrix[j, :] * dataMatrix[j, :].T\n",
    "                if eta >= 0:\n",
    "                    print('eta >= 0')\n",
    "                    continue\n",
    "                alphas[j] -= labelMat[j] * (Ei - Ej) / eta\n",
    "                alphas[j] = clipAlpha(alphas[j], H, L)\n",
    "                if abs(alphas[j] - alphaJold) < 0.00001:\n",
    "                    print('j not moving enough')\n",
    "                    continue\n",
    "                alphas[i] += labelMat[j] * labelMat[i] * (alphaJold - alphas[j])\n",
    "                b1 = b - Ei - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i, :] * dataMatrix[i, :].T -  labelMat[j] * (alphas[j] - alphaJold) * dataMatrix[i, :] * dataMatrix[j, :].T\n",
    "                b2 = b - Ej - labelMat[i] * (alphas[i] - alphaIold) * dataMatrix[i, :] * dataMatrix[j, :].T - labelMat[j] * (alphas[j] - alphaJold) * dataMatrix[j, :] * dataMatrix[j, :].T\n",
    "\n",
    "                if (0 < alphas[i]) and (C > alphas[i]):\n",
    "                    b = b1\n",
    "                elif (0 < alphas[j]) and (C > alphas[j]):\n",
    "                    b = b2\n",
    "                else:\n",
    "                    b = (b1 + b2) / 2.0\n",
    "                alphaPairsChanged += 1\n",
    "                print('iters: %d i: %d, pairs changed %d' % \n",
    "                     (iters, i, alphaPairsChanged))\n",
    "        if alphaPairsChanged == 0:\n",
    "            iters += 1\n",
    "        else:\n",
    "            iters = 0\n",
    "        print('iteration number: %d' % iters)\n",
    "    return b, alphas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b, alphas = smoSimple(dataArr, labelArr, 0.6, 0.001, 40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "alphas[alphas > 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "shape(alphas[alphas > 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 查找支持向量的数据点\n",
    "for i in range(100):\n",
    "    if alphas[i] > 0.0:\n",
    "        print(dataArr[i], labelArr[i])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SMO算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class optStruct:\n",
    "    def __init__(self, dataMatIn, classLabels, C, toler):\n",
    "        self.X = dataMatIn\n",
    "        self.labelMat = classLabels\n",
    "        self.C = C\n",
    "        self.tol = toler\n",
    "        self.m = shape(dataMatIn)[0]\n",
    "        self.alphas = mat(zeros((self.m, 1)))\n",
    "        self.b = 0\n",
    "        self.eCache = mat(zeros((self.m, 2)))  # 第一列是是否有效位，第二列是实际的E值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcEk(oS, k):\n",
    "    fXk = float(multiply(oS.alphas, oS.labelMat).T * (oS.X * oS.X[k, :].T) + oS.b)\n",
    "    Ek = fXk - float(oS.labelMat[k])\n",
    "    return Ek\n",
    "\n",
    "#  用于选择第二个alpha\n",
    "def selectJ(i, oS, Ei):\n",
    "    maxK = -1\n",
    "    maxDeltaE = 0\n",
    "    Ej = 0\n",
    "    oS.eCache[i] = [1, Ei]\n",
    "    validEcacheList = nonzero(oS.eCache[:, 0].A)[0]\n",
    "    if len(validEcacheList) > 1:\n",
    "        for k in validEcacheList:\n",
    "            if k == i:\n",
    "                continue\n",
    "            Ek = calcEk(oS, k)\n",
    "            deltaE = abs(Ei - Ek)\n",
    "            if deltaE > maxDeltaE:\n",
    "                maxK = k\n",
    "                maxDeltaE = deltaE\n",
    "                Ej = Ek\n",
    "        return maxK, Ej\n",
    "    else:\n",
    "        j = selectJrand(i, oS.m)\n",
    "        Ej = calcEk(oS, j)\n",
    "    return j, Ej\n",
    "\n",
    "def updateEk(oS, k):\n",
    "    Ek = calcEk(oS, k)\n",
    "    oS.eCache[k] = [1, Ek]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def innerL(i, oS):\n",
    "    Ei = calcEk(oS, i)\n",
    "    if ((oS.labelMat[i] * Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i] * Ei > oS.tol) and (oS.alphas[i] > 0)):\n",
    "        j, Ej = selectJ(i, oS, Ei)\n",
    "        alphaIold = oS.alphas[i].copy()\n",
    "        alphaJold = oS.alphas[j].copy()\n",
    "        if oS.labelMat[i] != oS.labelMat[j]:\n",
    "            L = max(0, oS.alphas[j] - oS.alphas[i])\n",
    "            H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])\n",
    "        else:\n",
    "            L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)\n",
    "            H = min(oS.C, oS.alphas[j] + oS.alphas[i])\n",
    "        if L == H:\n",
    "            print('L == H')\n",
    "            return 0\n",
    "        eta = 2.0 * oS.X[i, :] * oS.X[j, :].T - oS.X[i, :] * oS.X[i, :].T - oS.X[j, :] * oS.X[j, :].T\n",
    "        if eta >= 0:\n",
    "            print('eta >= 0')\n",
    "            return 0\n",
    "        oS.alphas[j] -= oS.labelMat[j] * (Ei - Ej) / eta\n",
    "        oS.alphas[j] = clipAlpha(oS.alphas[j], H, L)\n",
    "        updateEk(oS, j)\n",
    "        if abs(oS.alphas[j] - alphaJold) < 0.00001:\n",
    "            print('j not moving enough')\n",
    "            return 0\n",
    "        oS.alphas[i] += oS.labelMat[j] * oS.labelMat[i] * (alphaJold - oS.alphas[j])\n",
    "        updateEk(oS, i)\n",
    "        b1 = oS.b - Ei - oS.labelMat[i] * (oS.alphas[i] - alphaIold) * oS.X[i, :] * oS.X[i, :].T - oS.labelMat[j] * (oS.alphas[j] - alphaJold) * oS.X[i, :] * oS.X[j, :].T\n",
    "        b2 = oS.b - Ej - oS.labelMat[i] * (oS.alphas[i] - alphaIold) * oS.X[i, :] * oS.X[j, :].T - oS.labelMat[j] * (oS.alphas[j] - alphaJold) * oS.X[j, :] * oS.X[j, :].T\n",
    "        if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]):\n",
    "            oS.b = b1\n",
    "        elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]):\n",
    "            oS.b = b2\n",
    "        else:\n",
    "            oS.b = (b1 + b2) / 2.0\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def smoP(dataMatIn, classLabels, C, toler, maxIter, kTup=('lin', 0)):\n",
    "    oS = optStruct(mat(dataMatIn), mat(classLabels).transpose(), C, toler)\n",
    "    iters = 0\n",
    "    entireSet = True\n",
    "    alphaPairsChanged = 0\n",
    "    while iters < maxIter and (alphaPairsChanged > 0 or entireSet):\n",
    "        alphaPairsChanged = 0\n",
    "        if entireSet:\n",
    "            for i in range(oS.m):\n",
    "                alphaPairsChanged += innerL(i, oS)\n",
    "            print('fullSet, iters: %d i:%d, pairs changed %d' % (iters, i, alphaPairsChanged))\n",
    "            iters += 1\n",
    "        else:\n",
    "            nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]\n",
    "            for i in nonBoundIs:\n",
    "                alphaPairsChanged += innerL(i, oS)\n",
    "                print('non-bound, iters: %d i:%d, pair changed %d' % (iters, i, alphaPairsChanged))\n",
    "            iters += 1\n",
    "        if entireSet:\n",
    "            entireSet = False\n",
    "        elif alphaPairsChanged == 0:\n",
    "            entireSet = True\n",
    "        print('iteration number: %d' % iters)\n",
    "    return oS.b, oS.alphas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "dataArr, labelArr = loadDataSet('testSet.txt')\n",
    "b, alphas = smoP(dataArr, labelArr, 0.6, 0.001, 40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcWs(alphas, dataArr, classLabels):\n",
    "    X = mat(dataArr)\n",
    "    labelMat = mat(classLabels).transpose()\n",
    "    m, n = shape(X)\n",
    "    w = zeros((n, 1))\n",
    "    for i in range(m):\n",
    "        w += multiply(alphas[i] * labelMat[i], X[i, :].T)\n",
    "    return w"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ws = calcWs(alphas, dataArr, labelArr)\n",
    "ws"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "datMat = mat(dataArr)\n",
    "datMat[0] * mat(ws) + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "labelArr[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 核函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def kernelTrans(X, A, kTup):\n",
    "    m, n = shape(X)\n",
    "    K = mat(zeros((m, 1)))\n",
    "    if kTup[0] == 'lin':\n",
    "        K = X * A.T\n",
    "    elif kTup[0] == 'rbf':\n",
    "        for j in range(m):\n",
    "            deltaRow = X[j, :] - A\n",
    "            K[j] = deltaRow * deltaRow.T\n",
    "        K = exp(K / (-1 * kTup[1]**2))\n",
    "    else:\n",
    "        raise NameError('Houston We Have a Problem -- that Kernel is not recognized')\n",
    "    return K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class optStruct:\n",
    "    def __init__(self, dataMatIn, classLabels, C, toler, kTup):\n",
    "        self.X = dataMatIn\n",
    "        self.labelMat = classLabels\n",
    "        self.C = C\n",
    "        self.tol = toler\n",
    "        self.m = shape(dataMatIn)[0]\n",
    "        self.alphas = mat(zeros((self.m, 1)))\n",
    "        self.b = 0\n",
    "        self.eCache = mat(zeros((self.m, 2)))  # 第一列是是否有效位，第二列是实际的E值\n",
    "        self.K = mat(zeros((self.m, self.m)))\n",
    "        for i in range(self.m):\n",
    "            self.K[:, i] = kernelTrans(self.X, self.X[i, :], kTup)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def innerL(i, oS):\n",
    "    Ei = calcEk(oS, i)\n",
    "    if ((oS.labelMat[i] * Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i] * Ei > oS.tol) and (oS.alphas[i] > 0)):\n",
    "        j, Ej = selectJ(i, oS, Ei)\n",
    "        alphaIold = oS.alphas[i].copy()\n",
    "        alphaJold = oS.alphas[j].copy()\n",
    "        if oS.labelMat[i] != oS.labelMat[j]:\n",
    "            L = max(0, oS.alphas[j] - oS.alphas[i])\n",
    "            H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])\n",
    "        else:\n",
    "            L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)\n",
    "            H = min(oS.C, oS.alphas[j] + oS.alphas[i])\n",
    "        if L == H:\n",
    "            print('L == H')\n",
    "            return 0\n",
    "        eta = 2.0 * oS.K[i, j] - oS.K[i, i].T - oS.K[j, j]\n",
    "        if eta >= 0:\n",
    "            print('eta >= 0')\n",
    "            return 0\n",
    "        oS.alphas[j] -= oS.labelMat[j] * (Ei - Ej) / eta\n",
    "        oS.alphas[j] = clipAlpha(oS.alphas[j], H, L)\n",
    "        updateEk(oS, j)\n",
    "        if abs(oS.alphas[j] - alphaJold) < 0.00001:\n",
    "            print('j not moving enough')\n",
    "            return 0\n",
    "        oS.alphas[i] += oS.labelMat[j] * oS.labelMat[i] * (alphaJold - oS.alphas[j])\n",
    "        updateEk(oS, i)\n",
    "        b1 = oS.b - Ei - oS.labelMat[i] * (oS.alphas[i] - alphaIold) * oS.K[i, i] - oS.labelMat[j] * (oS.alphas[j] - alphaJold) * oS.K[i, j]\n",
    "        b2 = oS.b - Ej - oS.labelMat[i] * (oS.alphas[i] - alphaIold) * oS.K[i, j] - oS.labelMat[j] * (oS.alphas[j] - alphaJold) * oS.K[j, j]\n",
    "        if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]):\n",
    "            oS.b = b1\n",
    "        elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]):\n",
    "            oS.b = b2\n",
    "        else:\n",
    "            oS.b = (b1 + b2) / 2.0\n",
    "        return 1\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcEk(oS, k):\n",
    "    fXk = float(multiply(oS.alphas, oS.labelMat).T * oS.K[:, k] + oS.b)\n",
    "    Ek = fXk - float(oS.labelMat[k])\n",
    "    return Ek"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def testRbf(k1 = 1.3):\n",
    "    dataArr, labelArr = loadDataSet('testSetRBF.txt')\n",
    "    b, alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, ('rbf', k1))\n",
    "    datMat = mat(dataArr)\n",
    "    labelMat = mat(labelArr).transpose()\n",
    "    svInd = nonzero(alphas.A > 0)[0]\n",
    "    sVs = datMat[svInd]\n",
    "    labelSV = labelMat[svInd]\n",
    "    print('there are %d Support Vectors' % shape(sVs)[0])\n",
    "    m, n = shape(datMat)\n",
    "    errorCount = 0\n",
    "    for i in range(m):\n",
    "        kernelEval = kernelTrans(sVs, datMat[i, :], ('rbf', k1))\n",
    "        predict = kernelEval.T * multiply(labelSV, alphas[svInd]) + b\n",
    "        if sign(predict) != sign(labelArr[i]):\n",
    "            errorCount += 1\n",
    "        print('the training error rate is: %f' % (float(errorCount) / m))\n",
    "        dataArr, labelArr = loadDataSet('testSetRBF2.txt')\n",
    "        errorCount = 0\n",
    "        datMat = mat(dataArr)\n",
    "        labelMat = mat(labelArr).transpose()\n",
    "        m, n = shape(datMat)\n",
    "        for i in range(m):\n",
    "            kernelEval = kernelTrans(sVs, datMat[i,:], ('rbf', k1))\n",
    "            predict = kernelEval.T * multiply(labelSV, alphas[svInd]) + b\n",
    "            if sign(predict) != sign(labelArr[i]):\n",
    "                errorCount += 1\n",
    "        print('the test error rate is: %f' % (float(errorCount) / m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def smoP(dataMatIn, classLabels, C, toler, maxIter, kTup=('lin', 0)):\n",
    "    oS = optStruct(mat(dataMatIn), mat(classLabels).transpose(), C, toler, kTup)\n",
    "    iters = 0\n",
    "    entireSet = True\n",
    "    alphaPairsChanged = 0\n",
    "    while iters < maxIter and (alphaPairsChanged > 0 or entireSet):\n",
    "        alphaPairsChanged = 0\n",
    "        if entireSet:\n",
    "            for i in range(oS.m):\n",
    "                alphaPairsChanged += innerL(i, oS)\n",
    "            print('fullSet, iters: %d i:%d, pairs changed %d' % (iters, i, alphaPairsChanged))\n",
    "            iters += 1\n",
    "        else:\n",
    "            nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]\n",
    "            for i in nonBoundIs:\n",
    "                alphaPairsChanged += innerL(i, oS)\n",
    "                print('non-bound, iters: %d i:%d, pair changed %d' % (iters, i, alphaPairsChanged))\n",
    "            iters += 1\n",
    "        if entireSet:\n",
    "            entireSet = False\n",
    "        elif alphaPairsChanged == 0:\n",
    "            entireSet = True\n",
    "        print('iteration number: %d' % iters)\n",
    "    return oS.b, oS.alphas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "testRbf()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 手写识别问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 将图像文本转化为向量\n",
    "def img2vector(filename):\n",
    "    returnVect = zeros((1, 1024))\n",
    "    fr = open(filename)\n",
    "    for i in range(32):\n",
    "        lineStr = fr.readline()\n",
    "        for j in range(32):\n",
    "            returnVect[0, 32*i+j] = int(lineStr[j])\n",
    "    return returnVect\n",
    "\n",
    "def loadImages(dirName):\n",
    "    from os import listdir\n",
    "    hwLabels =[]\n",
    "    trainingFileList = listdir(dirName)\n",
    "    m = len(trainingFileList)\n",
    "    trainingMat = zeros((m, 1024))\n",
    "    for i in range(m):\n",
    "        fileNameStr = trainingFileList[i]\n",
    "        fileStr = fileNameStr.split('.')[0]\n",
    "        classNumStr = int(fileStr.split('_')[0])\n",
    "        if classNumStr == 9: \n",
    "            hwLabels.append(-1)\n",
    "        else:\n",
    "            hwLabels.append(1)\n",
    "        trainingMat[i, :] = img2vector('%s/%s' % (dirName, fileNameStr))\n",
    "    return trainingMat, hwLabels\n",
    "\n",
    "def testDigits(kTup=('rbf', 10)):\n",
    "    dataArr, labelArr = loadImages('trainingDigits')\n",
    "    b, alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, kTup)\n",
    "    \n",
    "    datMat = mat(dataArr)\n",
    "    labelMat = mat(labelArr).transpose()\n",
    "    \n",
    "    svInd = nonzero(alphas.A > 0)[0]\n",
    "    sVs = datMat[svInd]\n",
    "    labelSV = labelMat[svInd]\n",
    "    print('there are %d Support Vectors' % shape(sVs)[0])\n",
    "    m, n = shape(datMat)\n",
    "    errorCount = 0\n",
    "    for i in range(m):\n",
    "        kernelEval = kernelTrans(sVs, datMat[i, :], kTup)\n",
    "        predict = kernelEval.T * multiply(labelSV, alphas[svInd]) + b\n",
    "        if sign(predict) != sign(labelArr[i]):\n",
    "            errorCount += 1\n",
    "    print('the training error rate is: %f' % (float(errorCount) / m))\n",
    "    dataArr, labelArr = loadImages('testDigits')\n",
    "    errorCount = 0\n",
    "    datMat = mat(dataArr)\n",
    "    labelMat = mat(labelArr).transpose()\n",
    "    m, n = shape(datMat)\n",
    "    for i in range(m):\n",
    "        kernelEval = kernelTrans(sVs, datMat[i, :], kTup)\n",
    "        predict = kernelEval.T * multiply(labelSV, alphas[svInd]) + b\n",
    "        if sign(predict) != sign(labelArr[i]):\n",
    "            errorCount += 1\n",
    "    print('the test error rate is: %f' % (float(errorCount) / m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "testDigits(('rbf', 20))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
